package com.wzp.algorithm.must;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

/**
 * 桶排序最好情况下使用线性时间O(n)，桶排序的时间复杂度，取决与对各个桶之间数据进行排序的时间复杂度，
 * 因为其它部分的时间复杂度都为O(n)。很显然，桶划分的越小，各个桶之间的数据越少，排序所用的时间也会越少。
 * 但相应的空间消耗就会增大。
 * <p>
 * 最佳情况：T(n) = O(n+k) 最差情况：T(n) = O(n+k) 平均情况：T(n) = O(n2)
 */
public class BucketSort {

    public static Integer[] bucketSort(int[] array) {
        int max = Arrays.stream(array).max().getAsInt();
        int min = Arrays.stream(array).min().getAsInt();

        int bucketNum = (max - min) / array.length + 1;
        ArrayList<Integer>[] bucketArr = new ArrayList[bucketNum];

        for (int i = 0; i < array.length; i++) {
            int num = (array[i] - min) / array.length;
            if (bucketArr[num] == null) {
                bucketArr[num] = new ArrayList<>();
            }
            bucketArr[num].add(array[i]);
        }

        ArrayList<Integer> temp = new ArrayList<>();
        for (int i = 0; i < bucketArr.length; i++) {
            if (bucketArr[i] != null) {
                Collections.sort(bucketArr[i]);
                temp.addAll(bucketArr[i]);
            }
        }
        return temp.toArray(new Integer[temp.size()]);
    }

    public static void main(String[] args) {
        int[] array = new int[]{42, 19, 18, 35, 99, 12, 76};

        System.out.println("insertSort result:" + Arrays.toString(bucketSort1(array)));
//        System.out.println("insertSort result:" + Arrays.toString(bucketSort(array)));
    }

    public static Integer[] bucketSort1(int[] array) {
        int max = Arrays.stream(array).max().getAsInt();
        int min = Arrays.stream(array).min().getAsInt();

        int bucketNum = (max - min) / array.length + 1;
        ArrayList<Integer>[] bucketArr = new ArrayList[bucketNum];
        for (int i = 0; i < array.length; i++) {
            int index = (array[i] - min) / array.length;
            if(bucketArr[index] == null){
                bucketArr[index] = new ArrayList<>();
            }
            bucketArr[index].add(array[i]);
        }

        ArrayList<Integer> tmp = new ArrayList<>();
        for (int i = 0; i < bucketArr.length; i++) {
            if(bucketArr[i]!=null){
                Collections.sort(bucketArr[i]);
                tmp.addAll(bucketArr[i]);
            }
        }

        return tmp.toArray(new Integer[tmp.size()]);
    }

}
